package com.kevin.Code.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname ConvertBsttoGreaterTree
 * @Description Leetcode 538. 把二叉搜索树转换为累加树 中等难度  hot100
 * @Date 2021/11/22 20:20
 * @Version 1.0
 */
public class ConvertBsttoGreaterTree {
    int sum = 0;

    /**
     * 利用二叉搜索树的性质  我感觉写的还行啊
     *
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        List<Integer> combine = new ArrayList<>();
        int i = dfs(root, 0);
        return root;
    }


    public int dfs(TreeNode root, int preSum) {
        if (root == null) {
            return 0;
        }

        int right = dfs(root.right, preSum);
        //对presum重新赋值
        //获取右结点的值
        preSum = right == 0 ? preSum : right;
        preSum = preSum + root.val;
        root.val = preSum;

        int left = dfs(root.left, preSum);
        preSum = left == 0 ? preSum : left;
        return preSum;
    }

    /**
     * 官方题解
     *
     * @param root
     * @return
     */
    public TreeNode convertBST1(TreeNode root) {

        if (root != null) {
            convertBST(root.right);
            sum = root.val + sum;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }

    public static void main(String[] args) {

    }
}
